class DDLNode {
    int data;
    DDLNode previous;
    DDLNode next;

    public DDLNode(int data) {
        this.data = data;
    }

    public DDLNode() {
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public DDLNode getPrevious() {
        return previous;
    }

    public void setPrevious(DDLNode previous) {
        this.previous = previous;
    }

    public DDLNode getNext() {
        return next;
    }

    public void setNext(DDLNode next) {
        this.next = next;
    }

}

class DoubleLinkedList{
    private DDLNode headnode = new DDLNode(0);
    /**
     * 遍历链表，返回单向链表长度
     * @param headNode：链表头结点
     * @return length: 链表长度
     */
    int DDLListLength(DDLNode headNode){
        int length = 0;
        DDLNode currentNode = headNode;
        while(currentNode != null){
            length++;
            currentNode = currentNode.getNext();
        }
        return length;
    }

    /**
     * 双向链表插入节点
     * @param headNode:链表头节点
     * @param nodeToInsert:链表插入节点
     * @param position:相对于头结点位置
     * @return:返回头结点
     */
    DDLNode DDLInsert(DDLNode headNode, DDLNode nodeToInsert, int position){
        if(headNode == null){
            return nodeToInsert;
        }
        int size = DDLListLength(headNode);
        if(position < 1 || position > size + 1){
            System.out.println("输入不合法");
            return headNode;
        }

        if(position == 1){
            nodeToInsert.setNext(headNode);
            headNode.setPrevious(nodeToInsert);
            return nodeToInsert;
        }else{
            DDLNode previousNode = headNode;
            int count = 1;
            while(count < position - 1){
                previousNode = previousNode.getNext();
                count++;
            }
            DDLNode currentNode = previousNode.getNext();
            nodeToInsert.setNext(currentNode);
            if(currentNode == null){
                currentNode.setPrevious(nodeToInsert);
            }
            previousNode.setNext(nodeToInsert);
            nodeToInsert.setPrevious(previousNode);
        }
        return headNode;
    }

    /**
     * 双向链表中删除节点
     * @param headNode:链表头结点
     * @param position:相对于头结点位置
     * @return 返回头节点
     */
    DDLNode DDLDelete(DDLNode headNode, int position){
        int size = DDLListLength(headNode);
        if(position < 1 || position > size){
            System.out.println("输入不合法");
            return headNode;
        }
        if(position == 1){
            DDLNode currentNode = headNode.getNext();
            headNode = null;
            currentNode.setPrevious(null);
            return currentNode;
        }else{
            DDLNode previousNode = headNode;
            int count = 1;
            while(count < position - 1){
                count++;
                previousNode = previousNode.getNext();
            }
            DDLNode currentNode = previousNode.getNext();
            DDLNode laterNode = currentNode.getNext();
            previousNode.setNext(laterNode);
            if(laterNode != null){
                laterNode.setPrevious(previousNode);
            }
            currentNode = null;
        }
        return headNode;
    }

    /**
     * 打印链表
     */
    public void printDDLList() {
        if(headnode.next == null){
            System.out.println("链表为空");
            return;
        }

        DDLNode node = headnode.next;
        while(node != null) {
            System.out.println(node.getData());
            node = node.getNext();
        }
    }

    /**
     * 添加链表元素
     * @param headNode:头结点
     */
    public void addDDLList(DDLNode headNode){
        DDLNode temp = headnode;
        while (true){
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = headNode;
    }
}

class DDLNodeTest {
    public static void main(String[] args) {
        DDLNode firstNode = new DDLNode(1);
        DDLNode secondNode = new DDLNode(2);
        DDLNode thirdNode = new DDLNode(3);
        DDLNode fourthNode = new DDLNode(4);

        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addDDLList(firstNode);
        doubleLinkedList.addDDLList(secondNode);
        doubleLinkedList.addDDLList(thirdNode);

        System.out.println("插入之前的单向链表序列:");
        doubleLinkedList.printDDLList();

        doubleLinkedList.DDLInsert(secondNode,fourthNode,2);

        System.out.println("插入之后的单向链表序列:");
        doubleLinkedList.printDDLList();

        doubleLinkedList.DDLDelete(secondNode,2);

        System.out.println("删除之后的单向链表序列:");
        doubleLinkedList.printDDLList();
    }
}
